/// @tags: MatrixTree OGF
#include <cstdio>
#include <cstring>
#include <iostream>

using namespace std;

namespace BlueQuantum {

typedef long long LL;

int const N = 31, W = 152505, P = 998244353;

int u[N * N], v[N * N], w[N * N], phi[W], pri[50005];
bool vis[W];

inline int add(int x, int y) {
  if ((x += y) >= P) x -= P;
  return x;
}

inline int dec(int x, int y) {
  if ((x -= y) < 0) x += P;
  return x;
}

inline LL qpow(LL base, LL exp) {
  LL res = 1;
  while (exp) {
    if (exp & 1) res = res * base % P;
    base = base * base % P;
    exp >>= 1;
  }
  return res;
}

struct Polynomial {
  int x0, x1;

  Polynomial(int x0 = 0, int x1 = 0) : x0(x0), x1(x1) {}

  inline int zero() { return x0 ? 0 : (x1 ? 1 : 2); }

  inline Polynomial operator+(Polynomial const &rhs) const {
    return Polynomial(add(x0, rhs.x0), add(x1, rhs.x1));
  }
  inline Polynomial operator-(Polynomial const &rhs) const {
    return Polynomial(dec(x0, rhs.x0), dec(x1, rhs.x1));
  }
  inline Polynomial operator*(Polynomial const &rhs) const {
    return Polynomial((LL)x0 * rhs.x0 % P, add((LL)x0 * rhs.x1 % P, (LL)x1 * rhs.x0 % P));
  }
  inline Polynomial operator/(Polynomial const &rhs) const {
    if (x0 == 0 && rhs.x0 == 0) return Polynomial(x1 * qpow(rhs.x1, P - 2) % P, 0);
    LL inv = qpow(rhs.x0, P - 2);
    return Polynomial(x0 * inv % P,
                      dec((LL)x1 * rhs.x0 % P, (LL)x0 * rhs.x1 % P) * inv % P * inv % P);
  }
} mat[N][N];

inline void prework() {
  int cnt = 0;
  phi[1] = 1;
  for (int i = 2; i < W; ++i) {
    if (!vis[i]) pri[++cnt] = i, phi[i] = i - 1;
    for (int j = 1; j <= cnt && i * pri[j] < W; ++j) {
      vis[i * pri[j]] = true;
      if (i % pri[j] == 0) {
        phi[i * pri[j]] = phi[i] * pri[j];
        break;
      }
      phi[i * pri[j]] = phi[i] * (pri[j] - 1);
    }
  }
}

inline int getDET(int n) {
  bool f = true;
  for (int i = 1; i <= n; ++i) {
    int tar = i;
    for (int j = i + 1; j <= n; ++j)
      if (mat[j][i].zero() < mat[tar][i].zero()) tar = j;
    if (tar != i) swap(mat[i], mat[tar]), f ^= true;
    if (mat[i][i].zero() == 2) return 0;
    for (int j = i + 1; j <= n; ++j) {
      Polynomial t = mat[j][i] / mat[i][i];
      for (int k = i; k <= n; ++k) mat[j][k] = mat[j][k] - mat[i][k] * t;
    }
  }
  Polynomial res(f ? 1 : P - 1, 0);
  for (int i = 1; i <= n; ++i) res = res * mat[i][i];
  return res.x1;
}

inline int main() {
  prework();
  int n, m;
  cin >> n >> m, n--;
  int maxw = 0;
  for (int i = 1; i <= m; ++i) cin >> u[i] >> v[i] >> w[i], maxw = max(maxw, w[i]);
  int ans = 0;
  for (int i = 1; i <= maxw; ++i) {
    memset(mat, 0, sizeof(mat));
    int e_cnt = 0;
    for (int j = 1; j <= m; ++j)
      if (w[j] % i == 0) {
        mat[u[j]][v[j]] = mat[u[j]][v[j]] - Polynomial(1, w[j]);
        mat[v[j]][u[j]] = mat[v[j]][u[j]] - Polynomial(1, w[j]);
        mat[u[j]][u[j]] = mat[u[j]][u[j]] + Polynomial(1, w[j]);
        mat[v[j]][v[j]] = mat[v[j]][v[j]] + Polynomial(1, w[j]);
        e_cnt++;
      }
    if (e_cnt >= n - 1) {
      ans += (LL)getDET(n) * phi[i] % P;
      if (ans >= P) ans -= P;
    }
  }
  cout << ans;
  return 0;
}

}  // namespace BlueQuantum

int main() {
#ifndef ONLINE_JUDGE
#ifdef LOCAL
  freopen("/tmp/CodeTmp/testdata.in", "r", stdin);
  freopen("/tmp/CodeTmp/testdata.out", "w", stdout);
#else
  freopen("P6624 [省选联考 2020 A 卷] 作业题.in", "r", stdin);
  freopen("P6624 [省选联考 2020 A 卷] 作业题.out", "w", stdout);
#endif
#endif

  ios::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
  return BlueQuantum::main();
}
